package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.DataGeneratorUtil;
import com.chengqs.leetcode.utils.TimeCostUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 滑动窗口<br>
 * 哈希表、字符串、滑动窗口<br>
 * 中等
 *
 * <h1>438. 找到字符串中所有字母异位词</h1>
 *
 * <p>给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。</p>
 */
public class C09FindAnagrams {
    public static void main(String[] args) {
        C09FindAnagrams findAnagrams = new C09FindAnagrams();

        String s = "cbaebabacd", p = "abc";

        TimeCostUtil.timeCost("滑动窗口", () -> findAnagrams.solution1(s, p));
        TimeCostUtil.timeCost("滑动窗口", () -> findAnagrams.solution1_mine(s, p));
        TimeCostUtil.timeCost("优化的滑动窗口", () -> findAnagrams.solution2(s, p));

        String str = DataGeneratorUtil.generateRandomString(10000000);
        TimeCostUtil.timeCost("滑动窗口", () -> findAnagrams.solution1(str, p));
        TimeCostUtil.timeCost("滑动窗口_排序_自己写的方法", () -> findAnagrams.solution3_mine(str, p));
        TimeCostUtil.timeCost("滑动窗口_自己写的方法", () -> findAnagrams.solution1_mine(str, p));
        TimeCostUtil.timeCost("优化的滑动窗口", () -> findAnagrams.solution2(str, p));
    }

    /**
     * 先排序再比较，速度太慢了
     * @param s
     * @param p
     * @return
     */
    public List<Integer> solution3_mine(String s, String p) {
        // 滑动窗口大小
        int win = p.length();
        List<Integer> ans = new ArrayList<>();
        char[] chars = p.toCharArray();
        Arrays.sort(chars);
        String sortedP = new String(chars);
        for (int i = 0; i < s.length() - win + 1; i++) {
            String substring = s.substring(i, i + win);
            char[] subChars = substring.toCharArray();
            Arrays.sort(subChars);
            if (sortedP.equals(new String(subChars))) {
                ans.add(i);
            }
        }
        return ans;
    }

    public List<Integer> solution1_mine(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        ArrayList<Integer> ans = new ArrayList<>();

        if (sLen < pLen) {
            return ans;
        }
        int[] sCount = new int[26]; // 滑动窗口
        int[] pCount = new int[26]; // 存储字符串中每个字符出现的次数（与其匹配的异位词）
        for (int i = 0; i < pLen; i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 1; i < sLen - pLen + 1; i++) {
            // 窗口右移，将上个循环的索引从窗口计数中删掉，并将当前窗口右边界索引加入窗口计数中
            sCount[s.charAt(i - 1) - 'a']--;
            sCount[s.charAt(i + pLen - 1) - 'a']++;

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i);
            }
        }
        return ans;
    }

    // 滑动窗口
    public List<Integer> solution1(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }

    // 优化的滑动窗口
    public List<Integer> solution2(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }

        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }

        if (differ == 0) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s.charAt(i) - 'a'];

            if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];

            if (differ == 0) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}
